package dmsxl.zifuchuan;

import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2023/4/18 21:42
 * 翻转字符串II
 */
public class zfc2_541 {

    public static void main(String[] args) {
//        String s = "abcdefg";
        String s = "abcd";
        int k = 2;
        System.out.println(reverseStr(s, k));
    }

//    自己写的，效果奇差，时间和空间都是5%左右
    public static String reverseStr1(String s, int k) {
        String res = "";
        while (s.length() >= 2*k){
            res += reverse(s.substring(0, k));
            res += s.substring(k, 2*k);
            s = s.substring(2*k, s.length());
        }
        if (s.length() < k) res += reverse(s);
        if (s.length() >= k && s.length() < 2*k){
            String temp = reverse(s.substring(0, k));
            res = res + temp + s.substring(k, s.length());
        }
        return res;
    }

    public static String reverse(String s){
        char[] chars = s.toCharArray();
        int l = 0, r = s.length() - 1;
        while (l <= r){
            char temp = chars[l];
            chars[l] = chars[r];
            chars[r] = temp;
            l ++ ;
            r -- ;
        }
//        System.out.println(Arrays.toString(chars));
        return new String(chars);
    }

//    题解一，较好
    public static String reverseStr2(String s, int k) {
        StringBuffer res = new StringBuffer();
        int length = s.length();
        int start = 0;
        while (start < length) {
            // 找到k处和2k处
            StringBuffer temp = new StringBuffer();
            // 与length进行判断，如果大于length了，那就将其置为length
            int firstK = (start + k > length) ? length : start + k;
            int secondK = (start + (2 * k) > length) ? length : start + (2 * k);

            //无论start所处位置，至少会反转一次
            temp.append(s.substring(start, firstK));
            res.append(temp.reverse());

            // 如果firstK到secondK之间有元素，这些元素直接放入res里即可。
            if (firstK < secondK) { //此时剩余长度一定大于k。
                res.append(s.substring(firstK, secondK));
            }
            start += (2 * k);
        }
        return res.toString();
    }

//    题解二，较好
    public static String reverseStr3(String s, int k) {
        char[] ch = s.toCharArray();
        for(int i = 0; i < ch.length; i += 2 * k){
            int start = i;
            //这里是判断尾数够不够k个来取决end指针的位置
            int end = Math.min(ch.length - 1, start + k - 1);
            //用异或运算反转
            while(start < end){
                ch[start] ^= ch[end];
                ch[end] ^= ch[start];
                ch[start] ^= ch[end];
                start++;
                end--;
            }
        }
        return new String(ch);
    }

//    题解三，题解二的变体，较好
    public static String reverseStr4(String s, int k) {
        char[] ch = s.toCharArray();
        for(int i = 0;i < ch.length;i += 2 * k){
            int start = i;
            // 判断尾数够不够k个来取决end指针的位置
            int end = Math.min(ch.length - 1,start + k - 1);
            while(start < end){

                char temp = ch[start];
                ch[start] = ch[end];
                ch[end] = temp;

                start++;
                end--;
            }
        }
        return new String(ch);
    }

//    题解四，效率最好
    public static String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        // 1. 每隔 2k 个字符的前 k 个字符进行反转
        for (int i = 0; i< ch.length; i += 2 * k) {
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= ch.length) {
                reverse1(ch, i, i + k -1);
                continue;
            }
            // 3. 剩余字符少于 k 个，则将剩余字符全部反转
            reverse1(ch, i, ch.length - 1);
        }
        return  new String(ch);
    }

    // 定义翻转函数
    public static void reverse1(char[] ch, int i, int j) {
        for (; i < j; i++, j--) {
            char temp  = ch[i];
            ch[i] = ch[j];
            ch[j] = temp;
        }

    }
}
